Coordination and Bargaining over the Gaussian Interference Channel Xi Liu and Elza Erkip ECE Department, Polytechnic Institute of NYU, Brooklyn, NY 11201 Email; xliu02@students.poly.edu, elza@poly.edu o oo C/2 > m en o o X Abstract — This work considers coordination and bargaining between two selfish users over a Gaussian interference channel using game theory. The usual information theoretic approach assumes full cooperation among users for codebools and rate selection. In the scenario investigated here, each selfish user is willing to coordinate its actions only when an incentive exists and benefits of cooperation are fairly allocated. To improve communication rates, the two users are allowed to negotiate for the use of a simple Han-Kobayashl type scheme with fixed power split and conditions for which users have incentives to cooperate are identified. The Nash bargaining solution (NBS) is used as a tool to get fair information rates. The operating point is obtained as a result of an optimization problem and compared with a TDM-based one in the literature. I. Introduction Interference channel (IC) is a fundamental model in in- formation theory for studying interference in communication systems. In this model, multiple senders transmit independent messages to their corresponding receivers via a common chan- nel. The capacity region or the sum-rate capacity for the two- user Gaussian IC is only known in special cases such as the strong interference case |[I| lE] or the noisy interference case |[3l ; the characterization of the capacity region for the general case remains an open problem. Recently, it has been shown in that a simplified version of a scheme due to Han and Kobayashi ||2| results in an achievable rate region that is within one bit of the capacity region of the complex Gaussian IC. However, any type of Han-Kobayashi (H-K) scheme requires full cooperatiorU between the two users through the choice of transmission strategy. In practice, users are selfish in the sense that they choose a transmission strategy to maximize their own rates. They may not have an incentive to comply with a certain rule as in the H-K scheme and therefore not all rate pairs in an achievable rate region are actually attainable. When there is no coordination among the users, interference is usually treated as noise, which is information theoretically suboptimal in most cases. In this paper, we study a scenario where two users operating over a Gaussian IC are selfish but willing to coordinate and This material is based upon work partially supported by NSF Grant No. 0635177, by the Center for Advanced Technology in Telecommunications (CATT) of Polytechnic Institute of NYU. 'Throughout the paper, "cooperation" means cooperation for the choice of transmission strategy including codebook and rate selection, which is different from cooperation in information transmission as in cooperative communications. bargain to get good and fair information rates. When users have conflicting interests, the problem of achieving efficiency and fairness could be formulated as a game-theoretical prob- lem. The Gaussian IC was studied using noncooperative game theory in Q ||6|, where it was assumed that the receivers treat the interference as Gaussian noise. For the related Gaussian multiple-access channel (MAC), it was shown in Q that in a noncooperative rate game with two selfish users choosing their transmission rates independently, all points on the dominant face of the capacity region are pure strategy Nash Equilibria (NE). However, no single NE is superior to the others, making it impossible to single out one particular NE to operate at. The authors resorted to a mixed strategy which is inefficient in performance. Noncooperative information theoretical games were considered by Berry and Tse assuming that each user can select any encoding and decoding strategy to maximize its own rate and a Nash equilibrium region was characterized for a class of deterministic IC's |8|. Extensions were made to a symmetric Gaussian IC in ||9|. Another game theoretical approach for interfering links is due to Han et al. fTol, where the NBS from cooperative game theory was used as a tool to develop a fair resource allocation algorithm for uplink multi- cell OFDMA systems. Reference (TT] analyzed the NBS over the flat and frequency selective fading IC for time or frequency division multiplexing (TDM/FDM). The emphasis there was on the weak interference case. However, as we will show later, for the strong and mixed interference regimes, the NBS based on TDM/FDM may not perform very well, due to the suboptimality of TDM/FDM in those regimes. In this work, assuming each user is selfish but willing to coordinate its action when an incentive exists, we formulate the interaction between the two users as a bargaining problem. We first illustrate how selfish users can bargain for a fair rate allocation over a Gaussian MAC. We then propose a two-phase mechanism for coordination between users over the Gaussian IC. First, the two users negotiate and only if certain incentive conditions are satisfied they agree to use a simple H-K type scheme with a fixed power split that gives the optimal or close to optimal sets of achievable rates |4|. In the second phase, the NBS is used as a fairness criterion to obtain a preferred operating point over the achievable rate region. For all values of channel parameters, we study the incentive conditions for users to coordinate their transmissions. We also formulate the computation of the NBS over the H-K rate region as a convex optimization problem. Results show that the NBS exhibits significant rate improvements for both users compared with the uncoordinated case. The NBS obtained here can also achieve the maximum sum rate of the adopted H-K scheme in most cases, which demonstrates its strong efficiency. II. System Model A. Channel Model In this paper, we focus on the two-user standard Gaussian IC Y2 = VbXi +X2 + Z2 (1) (2) where Xi and Yi represent the input and output of user i g {1,2}, respectively, and Zi and Z2 are i.i.d. Gaussian with zero mean and unit variance. Receiver i is only interested in the message sent by transmitter i. Constants y/a and ^/b represent the real- valued channel gains of the interfering links. If a > 1 and & > 1, the channel is strong Gaussian IC; if either < a < 1 and & > 1, or < 6 < 1 and a > 1, the channel is mixed Gaussian IC; if < a < 1 and < 5 < 1, the channel is weak Gaussian IC. We assume that transmitter of user i, i e {1,2}, is subject to an average power constraint Pi. We let SNRi — Pi be the signal to noise ratio (SNR) of user i. B. Achievable Rate Region The best known inner bound for the two-user Gaussian IC is the full H-K achievable region |2|. Even when the input distributions in the H-K scheme are restricted to be Gaussian, computation of the full H-K region remains difficult due to numerous degrees of freedom involved in the problem |12|. Therefore we assume users employ Gaussian codebooks with equal length codewords and consider a simplified H-K type scheme with fixed power split and no time-sharing as in jj. Let a G [0, 1] and (3 e [0, 1] denote the fractions of power allocated to the private messages (messages only to be decoded at intended receivers) of user 1 and user 2 respectively. We define T as the collection of all rate pairs (i?i,i?2) G K^ satisfying ■ Pi i?i < 01 = C R2<h = C 1 + apP2 P2 with 1 + baPi , Ri+ R2 <(f>3^ min{03i, (/)32>33} .3.=C(^±ifc^Uc^ /3P. '/'32 = C 1 + a/3P2 aPi 1 + baPi (3) (4) (5) (6) 1 + a/3P2 C(^±^ii-^^~| (7) ^33 -i ^^^^^^1^1- 1 + baPi PP2 + b{l - a)Pi 1 + baPi and 2i?i + i?2 < 04 = C Ri + 2R2 < +C c +c Pi + a(l - f3)P2 1 + a/3P2 / /3P2+b(l-a)Pi V 1 + baPi P2 + 6(1 - a)Pi 1 + baPi aPi + q(1 - (3)P2 1 + a/3P2 C aPi C 1 + a/3P2 (9) /3P2 1 + baPi (10) where C{x) — l/21og2(l + x). The region J^ is a polytope and a function of a and /?. We denote the H-K scheme that achieves the rate region F by HK(q;, j3). For convenience, we also represent J^ in a matrix form as J^ = {R|R > 0, R < Ri, and AR < B}, where R = (Pi P2)*, R^ = (0i ^2)*, B ^3 04 05)*, and 1 2 1 1 1 2 (11) (8) Throughout the paper, for any two vectors U and V, we denote U > V if and only if U., > V, for alH. U < V, U > V and U < V are defined similarly. C. Nash Bargaining Solution We employ the NBS as a criterion for selecting the desired operating point from a given achievable rate region, due to its Pareto optimality and fairness. In the following, we briefly review the basic concepts and results for the NBS in the context of our problem. More details are provided in Section III and Section IV. We denote by P° the rate user i would expect when both treat each other's signals as Gaussian noise. So we have ^? = C(TTk) ^"'l ^2 = Cij^). We choose R" = (Pi P2)* as the disagreement point, i.e., when negotiation breaks down, both users can transmit without cooperation at rates in R*'. The bargaining problem can be represented by the pair {T, R"). We say {T, R°) is essential iff there exists at least one allocation R' in T that is strictly better for both users than R*^, i.e., the set J^D {R|R > R"} is nonempty. In order for both users to have incentives for cooperation, it is required that (J^, R") be essential; otherwise, at least one user does not have the incentive to bargain. A payoff allocation R is said to be Pareto optimal iff there is no other allocation R' such that R[ > Ri.^i, and 3i, R[ > Ri. This bargaining problem is approached axiomatically by Nash L13J. R* = *(J",R0) is said to be an NBS in T for R°, if the following axioms are satisfied. 1) Individual Rationality: $,(J",R°) >R^yi 2) Feasibility: *(J",Rf') e T 3) Pareto Optimality: 4>(J^, R") is Pareto optimal. 4) Independence of Irrelevant Alternatives: For any closed convex set tj, if CJ C J" and *(J", R°) e Q, then *(g,RO) = *(J-,RO). 5) Scale Invariance: For any numbers Ai,A2,7i and 72, such that Ai > and A2 > 0, if tj = {(AiPi + 7i,A2i?2 +72)\iRi,R2) e ^} and u = (Aii?? + 7i,A2i?^ + 72), then ^{g,u) = (Ai$i(J',R") + 7l,A2$2(-^,R°)+72). 6) Symmetry: If i?? = i?^, and {{R2, Ri)\iRu R2) e J"} = J", then $i(J',RO) = $2(-7^,R°)- Axioms (4)-(6) are also called axioms of fairness. Theorem 1: fT3\ There is a unique solution ^{J-, R°) that satisfies all six axioms in the above, and is given by, 2 ^(J-, R°) = arg max 1[{R, - i?°) (12) The NBS selects the unique allocation that maximizes the Nash product in (12) over all feasible individual rational allocations. Note that for any essential bargaining problem, the Nash point should always satisfy R* > i?f,V«. III. Bargaining over the Two-User Gaussian MAC Before we move to the Gaussian IC, we first consider a Gaussian MAC in which two users send information to one common receiver This also forms the foundation for the solution of the strong IC. The received signal is given by Y = Xi+X2 Z (13) where Xi is the input signal of user i and Z is Gaussian noise with zero mean and unit variance. Each user has an individual average input power constraint Pi. The capacity region C is the set of all rate pairs (i?i, R2) such that Ri R^<C{Pi), I £{1,2} R2<^0 = C{Pi+P2) (14) (15) If the two users fully cooperate in codebook and rate selection, any point in C is achievable. When there is no coordination between users, in the worst case, one user's signal can be treated as noise in the decoding of the other user's signal, leading to rate i?° = C( ^_^_p' ) for user i. In Q, i?° is also called user i's "safe rate". If the two users are selfish but willing to coordinate for mutual benefits, they may bargain over C to obtain a fair operating point with R" serving as a disagreement point. Proposition 1: There exists a unique NBS for the bargain- ing problem (C,R"), given by R* == (i?J + ^,i?^ + ■\) where ^i^ = 4,,-1^1-r^ - Proof Maximizing the Nash product in (12) with F replaced by C is equivalent to maximizing its logarithm. Define /(R) = ln(i?i - R\) + ln(i?2 - Rl), then /(•) : C n {R|R > R"} -> R+ is a strictly concave function of R. Also note that the constraints in (12), (14) and (15) are linear in Ri and R2. So the first order Karush-Kuhn-Tucker conditions are necessary and sufficient for optimality [l4l. Let L(R, A, ^) denote the Lagrangian where A; > 0, i = 1, 2 and /ii > denote the Lagrange multipliers associated with the Boundary of MAC capacity region Disagreement point o NBS Fig. 1. The Nash point over the MAC when SNRi = 15dB, SNR2 = 20dB constraints, then we have 2 L(R, A, ^i) - /(R) + Y, \{R, - Rf) + Aii(<^o - i?i - R2) (16) The first-order necessary and sufficient conditions yield 1 + (A, - Ml) [R* - i?0) = 0; i = 1, 2 (17) and iR*^Rf)\,^0- A, >0;i = l,2 (18) {RI +R*2- 0o)/ii = 0; A^i > (19) Since R* > i?° must hold, we have Ai = for i ~ 1,2. Also the constraint cjjq — R^ — Ri, > has to be active, i.e., Rl + R*2= 00 (20) Solving (17) and (20), we obtain fn = , -^u_jfu and R* ~ i?° + ^,^ = l,2. " ' ' ■ In Fig. 1, the capacity region, the disagreement point and the NBS obtained using Proposition 1 are illustrated for SNRi = 15dB and SNR2 == 20dB. Recall that the mixed sti-ategy NE in |7| has an average performance equal to the safe rates in R°. The NBS point which is the unique fair Pareto-optimal point in C is component-wise superior This shows that bargaining can improve the rates for both of the selfish users in a MAC. IV. Two-User Gaussian IC For the IC, the coordination between the two users is done in two phases. In phase 1, they negotiate for a simple H-K type scheme that has the potential to improve individual rates for both. The private message power factors a, /3 in the H- K scheme are jointly determined by both users and depend on their power constraints P\, P2 and channel parameters a and h. If at least one user does not have the incentive to cooperate in the sense of Sec II-C, then negotiation breaks down; otherwise, they reach an agreement on the use of the H-K type scheme with the chosen power split. In phase 2, both users bargain for a fair rate pair in the bargaining set which is the achievable rate region of the H-K scheme they agreed on earlier. This problem can then be formulated as a two-user bargaining problem with the feasibility set T and disagreement point R". Once a particular rate pair is determined as the solution, related codebook information is shared between the users so that one user's receiver can decode the other user's common message as required by the adopted H-K scheme in agreement. If negotiation breaks down, each receiver is not provided with the interfering user's codebook. A. Conditions for users to have incentives to cooperate In this subsection, we discuss the incentive conditions for both users to cooperate and how they jointly choose a and /? for different interference regimes. In the first phase, the two users search for a H-K scheme that could result in a rate region containing rate pairs component-wise better than R'^. Intuitively, it would be best to have a scheme that could achieve the largest rate region that includes R'^. While the full H-K achievable region |2| needs to take into account all possible power splits and different time-sharing strategies, it is computationally infeasible. For tractability, we restrict the two users' choices to a simple H-K type scheme with fixed power split and no time-sharing. For the weak and mixed interference cases, we study incentive conditions for cooperation based on the near-optimal power split of |4|. For the strong interference case, we set a — (3 ~ 0, which is known to be optimal |1|. 1) Strong Interference: Suppose a > 1 and b > I, and we choose optimal a = f3 — 0. Treating interference as noise is suboptimal and R*' always lies inside T. The bargaining problem (J^, R°) is essential and hence both users always have incentives to cooperate. 2) Mixed Interference: Without loss of generality, we as- sume a < 1 and b > 1. We use the near-optimal power splits a ^0 and (3 = min(l/(aP2), 1) |4|. If aPj < 1, the interference from user 2 has a smaller effect on user 1 than the noise at user I's receiver does. The scheme HK(0, 1) will not improve user I's rate and hence user 1 does not have an incentive to cooperate using this scheme. But if aP2 > 1 and JTl {R > R°} is nonempty when a = and (3 = l/{aP2), it is possible to improve both users' rates relative to those in RO. Note that aP2 > 1 holds when a > 1/P2- When SNR2 is high, this condition is satisfied for most as. This implies that in the interference limited regimes, it is very likely that both users would have incentives to cooperate. The case for a > 1 and 6 < 1 can be analyzed similarly. 3) Weak Interference: Suppose a < 1 and b < 1. We use the power splits a — min(l/(6Pi), 1) and (3 — min(l/(aP2); 1) [4]. Similar to the mixed case, only if aP2 > 1, 6P1 > 1 and J" n {R > R°} is nonempty when a — l/(6Pi) and /3 — XjiaP^), both users' rates can be improved compared with those in R''. Note that as in the mixed case, when both SNR's are high, the conditions aP2 > 1 and bP\ > 1 are satisfied for most channel gains in the range and it only remains to check whether J^ n {R > R'^} is nonempty. B. Computing the Nash Bargaining Solution After the users agree on an H-K scheme, in phase 2, the NBS over the corresponding rate region F is employed as the operating point. We concentrate on the case when R° < B} and AR° < B so that J"n {R > R"} is nonempty. From Section II, we know that, the NBS exists for {F, R°) and is unique. It can be computed by optimizing (12). Proposition 2: Assuming that R" < R^ and AR° < B, there exists a unique NBS R* for the bargaining problem {F, YiP), which is characterized as follows: R* ^minlRl-R^i 2_/, = l Mj^ji , *e{l,2} (21) where jij >0,jG {1, 2, 3} is chosen to satisfy (AR* - B)j^ij = 0, AR* < B Proof As in the proof of Proposition 1, we use the La- grange multiplier method and Karush-Kuhn-Tucker optimality conditions. Due to limited space, the proof is omitted. ■ V. Illustration of Results The achievable rate region of the H-K scheme and the H-K NBS are plotted for different values of channel coefficients in Fig. 2. For comparison, we also include the TDM region and the TDM NBS. The TDM region is given by 7^TDM = {R|R = {piC{^) P2C(f ))*, p, > 0,V*, P1 + P2 < 1} and the TDM NBS is computed by optimizing (12) with F replaced by 7?.tdm- The NBS based on TDM was also investigated in 1 11 1 using the unique competitive solution studied there as the disagreement point. Since interference limited regimes are more of interest here, in these plots, we assume both SNR's are high, i.e, SNRi = SNR2 = 20dB. In Fig. 2(a), both interfering links are strong, hence HK(0,0) is employed. The H-K NBS strictly dominates the TDM one. Fig. 2(b) shows an example for mixed interference case when a = 0.1 and b ^ 3. Since aP2 = 10 > 1, HK(0,0.1) is employed. In this example, although TDM results in some rate pairs that are outside the H-K rate region, the H-K NBS remains component-wise betteiO than the TDM one. The weak interference case when a = 0.2 and 6 = 0.5 is plotted in Fig. 2(c). Given these parameters, we have aP2 = 20 > 1 and bPi = 50 > 1, therefore HK(0.02, 0.05) is used. The H-K NBS, though still much better than R'', is slightly worse than the TDM one. This is because the TDM rate region contains the H-K rate region due to the suboptimality of the simple H-K scheme in the weak regime. Note that we do not employ time sharing in the chosen H-K scheme. Finally, recall that while the TDM rate region does not depend on a and b, since R'^ does, the TDM NBS depends on a and b as well. We compute the H-K NBS for different ranges of the channel gains in Fig. 3. We assume SNRi = SNR2 = 20dB, a = 1.5 and b varies from to 3. For all 6's, both users' rates in the NBS R* are higher than those in R'^. The improvement of each user's rate in R* over the one in R° increases as b grows. When b < a, user I's rate in the NBS is less than user ^Note this may not necessarily liold for all SNR's and the channel gains in the range. In other words, for some other parameters, it is possible that one user gets a higher rate in the TDM NBS than in the H-K NBS. 3.5 O H-K NBS - >.^ * r" ^ V Boundary ot TDM Region ''***«^^ •» □ TDM NBS ^^-^..^ <* tr" 2 1.5 1 0.5 \ \ 1 ^ (a) Strong interference a = 3, b = 5 (b) Mixed interference a = 0.1, 6 = 3 (c) Weak interference a = 0.2, b = 0.5 Fig. 2. Tlie H-K NBS of tlie Gaussian IC in different interference regimes when SNRi = SNR2 = 20dB. 2.6 N- 2 r, 1 '■',, ^ 1 ^^^_^ — -"^ 1 I 1-5 K 1 \ \ \ r', ^^2 , — ,R° 0.5 ---R° 1.5 b Fig. 3. Rates in the NBS R* and disagreement point R" when SNRi SNR2 = 20dB and a = 1.5. 4 3.9 . 3.8 3.7 ' 3.6 3.5 3.4 3.3 3.2 1 \^. t (H-K NBS) (TDM NBS) (H-K Sum Rate) ■ 1.5 b Fig. 4. a = 1.5. Sum rates in the H-K NBS when SNRi = SNR2 = 20dB and 2's; however, as b grows beyond a, user I's rate in the NBS surpasses user 2's, which is due to the fairness property of the NBS. Alternatively we say a strong interfering link can give user 1 an advantage in bargaining. In Fig. 4, we plot the sum rates for H-K NBS and TDM NBS under the same setting as in Fig. 3. For comparison, the maximum sum rate of the H-K scheme with the chosen power split is also given. The H-K NBS performs better in terms of sum rates than the TDM NBS for all 6's except when b is around 1, where the performances of the two schemes are similar Moreover, the H-K NBS rate pair can achieve the maximum sum rate of the H-K scheme used for almost all b's except when b is very small (< 0.05), the sum rate of the H-K NBS is relatively lower. This demonstrates that the H-K NBS not only provides a fair operating point but also maintains a good overall performance. VI. Conclusions In this paper, we investigated the two-user Gaussian IC, under the assumption that the two users are selfish and interested in cooperation only when they have incentives to do so. We proposed a two-phase mechanism for the two users to coordinate, which consists of choosing a simple H-K type scheme with Gaussian codebooks and fixed power split in phase 1 and bargaining over the achievable rate region to obtain a fair operating point in phase 2. We show that the proposed mechanism can gain substantial rate improvements for both users compared with the uncoordinated case. The obtained operating point is also strongly efficient in the sense that it can achieve the maximum sum rate of the adopted simple H-K type scheme in most cases. References [1] H. Sato, "The capacity of the Gaussian interference channel under strong interference," IEEE Trans. Inf. Theory, vol. 27, pp. 786-788, Nov. 1981. [2] T. S. Han and K. Kobayashi, "A new achievable rate region for the interference channel," IEEE Trans. IT, vol. 27, no. 1, pp. 49-60, 1981. [3] X. Shang, G. Kramer, and B. Chen, "A new outer bound and the noisy- interference sum-rate capacity for Gaussian interference channels," IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 689-699, 2009. [4] R.Etkin, D. Tse, and H. Wang, "Gaussian interference channel capacity to within one bit," IEEE Trans. IT, vol. 54, no. 12, pp. 5534-5562, 2008. [5] R.Etkin, A. Parekh, and D. Tse, "Spectrum sharing for unlicensed bands," IEEE J. Set Areas Commun., vol. 25, no. 3, pp. 517-528, 2007. [6] E. G. Larsson and E. A. Jorswieck, "Competition versus cooperation on the MISO interference channel," IEEE JSAC, vol. 26, no. 7, 2008. [7] V. Gajic and B. Rimoldi, "Game theoretic considerations for the Gaus- sian multiple access channel," in Proceedings of IEEE ISIT, Toronto, Canada, July 2008, pp. 2523-2527. [8] R. Berry and D. Tse, "Information theoretic games on interference channels," in Proceedings of IEEE ISIT, Toronto, Canada, July 2008. [9] , "Information theoiy meets game theory on the interference chan- nel," in Proceedings of IEEE ITW, Volos, Greece, June 2009. [10] Z. Han, Z. Ji, and K. J. R. Liu, "Fair multiuser channel allocation for OFDMA networks using Nash bargaining solutions and coaUtions," IEEE Trans. Commun., pp. 1366-1376, Aug. 2005. [II] A. Leshem and E. Zehavi, "Cooperative game theory and the Gaussian interference channel," IEEE JSAC, vol. 26, no. 7, pp. 1078-1088, 2008. [12] A. S. Motahari and A. K. Khandani, "Capacity bounds for the Gaussian interference channel," IEEE Trans. IT, vol. 55, no. 2, pp. 620-643, 2009. [13] R. B. Myerson, Game Theory. Harvard University Press, 1991. [14] D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.